package C034;

/**
 * ClassName: C03
 * Package: C034
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/5 10:37
 * @Version 1.0
 * @Since 1.0
 */
public class C03 {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.next = node2;
        node2.next = node3;
        Node node = copyRandomList(node1);

        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();

        while(node1 != null) {
            System.out.print(node1.val + " ");
            node1 = node1.next;
        }

    }
    public static Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }
        // 1 - 2 - 3
        // 1 - 1' - 2 - 2' - 3 - 3'
        Node mid = null, next;
        Node cur = head;
        while (cur != null) {
            mid = new Node(cur.val);
            next = cur.next;
            cur.next = mid;
            mid.next = next;
            cur = next;
        }

        // 设置随机指针
        cur = head;

        while (cur != null) {
            if (cur.random == null) {
                cur.next.random = null;
                cur = cur.next.next;
            } else {
                cur.next.random = cur.random.next;
                cur = cur.next.next;
            }
        }

        // 新旧链表分离
        Node h2 = head.next;
        cur = head;
        while(cur != null) {
            next = cur.next;
            cur.next = next.next;
            next.next = cur.next == null ? null : next.next.next;
            cur = cur.next;
        }

        return h2;
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
